# 抖码算法，让算法学习变得简单有趣
# 作者：老汤


class MergeSort:
    def sort(self, data):
        self.data = data.copy()
        self.dfs(0, len(self.data) - 1)
        data[:] = self.data

    def dfs(self, start, end):
        if start == end:
            return

        mid = (start + end) // 2
        self.dfs(start, mid)
        self.dfs(mid + 1, end)
        self.merge(start, mid, end)

    def merge(self, start, mid, end):
        i, j = start, mid + 1
        temp = []
        while i <= mid and j <= end:
            if self.data[i] < self.data[j]:
                temp.append(self.data[i])
                i += 1
            else:
                temp.append(self.data[j])
                j += 1
        while i <= mid:
            temp.append(self.data[i])
            i += 1
        while j <= end:
            temp.append(self.data[j])
            j += 1
        for k in range(start, end + 1):
            self.data[k] = temp[k - start]
